It seems that I write about superpermutations way too frequently, and today I’m going to continue the trend. Recall that a superpermutation is a string on n symbols that contains all n! permutations of those n symbols as contiguous substrings. For example, when n = 3, the 3! = 6 permutations of the symbols “1”, “2”, and “3” are 123, 132, 213, 231, 312, and 321, and a superpermutation is

123121321

since it contains all 6 of those permutations as substrings. That superpermutation is “minimal”: no shorter superpermutation on 3 symbols exists. We know how long minimal superpermutations are when n ≤ 5, but when n ≥ 6 determining this minimal length is still an open problem.

Somewhat surprisingly, there is a natural generalization of this problem that is actually easier to solve… in all cases except for the original case (superpermutations) that we care about. Here’s how it works: instead of requiring that the superstring contain all permutations as substrings, fix an additional parameter k that specifies the length of the substrings that it must contain. We say that a (length-k) string is injective if all of the characters in it are distinct, and we say that an injective superstring is a string that contains all injective strings (for a fixed pair of parameters n and k) as contiguous substrings. What is the minimal length of an injective superstring?

The requirement that the characters in an injective string be distinct forces the inequality k ≤ n. In the extreme case when k = n, an injective string is simply a permutation, so an injective superstring is simply a superpermutation, in which case the problem of finding a minimal one is hard. However, all other cases are easy: whenever k < n, it is known that minimal injective superstrings have length exactly equal to n!/(n-k)! + (k-1). For example, if n = 3 and k = 2 then the injective strings (strings of length 2 on the symbols “1”, “2”, and “3” in which all characters are distinct) are 12, 13, 21, 23, 31, and 32, and a minimal injective superstring (of length n!/(n-k)! + (k-1) = 6/1 + 2 = 8) is 1231321.

My latest video demonstrates how to construct minimal injective superstrings, and explains why they are so much easier to construct than minimal superpermutations:

Back in September 1995, David Buckingham showed how to construct oscillators and glider guns of any period at least 61 in Conway’s Game of Life. His method was based on a tool called a “Herschel conduit“; a configuration of still lifes that can be used to move a Herschel from one location to another. By stitching together several of these Herschel conduits, we can create a complete track for the Herschel to move around, thus creating an oscillator (or a gun, if we let the glider that the Herschel naturally creates escape).

Herschel tracks are still used constantly in Conway’s Game of Life, and I’m starting a series of video tutorials that show how they work. Part 1 is now up:

The pattern animations throughout the video were all made with Manim. Once I get a few more videos under my belt, and my code cleaned up a bit more, I’ll share my code for making pretty Life animations.

Lights Out is a puzzle that sits in a very interesting place mathematically: while many puzzles can be solved with the help of math, Lights Out is solved exactly and completely by math (linear algebra in particular). Linear algebra doesn’t just make it easier to solve: it finds an exact solution, and does it so cleanly that it seems like Lights Out was made for mathematical reasons (even though it wasn’t, unlike some other puzzles).

So if you’re ever stuck in a video game that has this puzzle (which seems to be just about all of them), just give the following video a quick watch and then whip out your favourite linear algebra software to solve a too-large-to-want-to-solve-by-hand linear system:

The Manim Python script for creating the animations in this video is attached below since, given how absurdly long it took to put together, it would be a shame if no one else made use of it for anything. So please, make use of it – make more videos about Lights Out!

• Manim Python script for the “Lights Out” video

I’ve been meaning to make a series of videos on Conway’s Game of Life for a few years now, and I finally decided that rather than rehashing topics that are already covered in the textbook, I’ll make videos explaining particularly notable new discoveries as they’re made. Unfortunately, the news that Life is omniperiodic is somewhat well-worn at this point, so I started this week with a video about the newly-discovered true period 15 and 16 glider guns (which are both the first guns of their respective periods ever found, and which were found less than 5 hours apart!):

The video does delve into some “rehashed” stuff, like what a B-heptomino is, and how guns work in general, but that’s unavoidable if I want the video to be understandable to more than 100 or so people in the world. Hopefully a few news videos like this might actually convince enough people that Life is interesting enough so as to bump that “100” number up in the near future!

After a 3-year hiatus, I’m back making math videos, not least of all thanks to my new fancy-schmancy basement studio:

This time I’m trying this crazy technique called “editing”, rather than just recording myself and dumping raw video footage online (which, believe it or not, is what I did for my previous videos – those were all recorded “live”). My first new video is now up, which investigates the problem of how to place 3 non-overlapping circles in a triangle so as to cover as much area as possible (a problem that is often incorrectly thought to have the Malfatti circles as its solution):

I used Manim for the triangle and circle animations and Capcut to edit everything together. I’m going to aim for one video per week or so, and hopefully will be able to put together a decent Applied Calculus playlist this summer.

One of the standard applications of orthogonal projections to function spaces comes in the form of Fourier series, where we use \(B = \{1,\cos(x),\sin(x),\cos(2x),\sin(2x),\ldots\}\) as a mutually orthogonal set of functions with respect to the usual inner product

\(\displaystyle\langle f, g \rangle = \int_{-\pi}^\pi f(x)g(x) \, \mathrm{d}x.\)

In particular, projecting a function onto the span of the first 2n+1 functions in the set \(B\) gives its order-n Fourier approximation:

\(\displaystyle f(x) \approx a_0 + \sum_{k=1}^n a_k \cos(kx) + \sum_{k=1}^n b_k \sin(kx),\)

where the coefficients \(a_0,a_1,a_2,\ldots,a_n\) and \(b_1,b_2,\ldots,b_n\) can be computed via inner products (i.e., integrals) in this space (see many other places on the web, like here and here, for more details).

A natural follow-up question is then whether or not we similarly get Taylor polynomials when we project a function down onto the span of the set of functions \(C = \{1,x,x^2,x^3,\ldots,x^n\}\). More specifically, if we define \(\mathcal{C}[-1,1]\) to be the inner product space consisting of continuous functions on the interval [-1,1] with the standard inner product

\(\displaystyle\langle f, g \rangle = \int_{-1}^1 f(x)g(x) \, \mathrm{d}x,\)

and consider the orthogonal projection \(P : \mathcal{C}[-1,1] \rightarrow \mathcal{C}[-1,1]\) with range equal to \(\mathcal{P}_n[-1,1]\), the subspace of degree-n polynomials, is it the case that \(P(e^x)\) is the degree-n Taylor polynomial of \(e^x\)?

It does not take long to work through an example to see that, no, we do not get Taylor polynomials when we do this. For example, if we choose n = 2 then projecting the function \(e^x\) onto the  \(\mathcal{P}_2[-1,1]\) results in the function \(P(e^x) \approx 0.5367x^2 + 1.1036x + 0.9963\), which is not its degree-2 Taylor polynomial \(p_2(x) = 0.5x^2 + x + 1\). These various functions are plotted below (\(e^x\) is displayed in orange, and the two different approximating polynomials are displayed in blue):

These plots illustrate why the orthogonal projection of \(e^x\) does not equal its Taylor polynomial: the orthogonal projection is designed to approximate \(e^x\) as well as possible on the whole interval [-1,1], whereas the Taylor polynomial is designed to approximate it as well as possible at x = 0 (while sacrificing precision near the endpoints of the interval, if necessary).

However, something interesting happens if we change the interval that the orthogonal projection acts on. In particular, if we let \(0 < c \in \mathbb{R}\) be a scalar and instead consider the orthogonal projection \(P_c : \mathcal{C}[-c,c] \rightarrow \mathcal{C}[-c,c]\) with range equal to \(\mathcal{P}_2[-c,c]\), then a straightforward (but hideous) calculation shows that the best degree-2 polynomial approximation of \(e^x\) on the interval [-c,c] is

While this by itself is an ugly mess, something interesting happens if we take the limit as c approaches 0:

\(\displaystyle\lim_{c\rightarrow 0^+} P_c(e^x) = \frac{1}{2}x^2 + x + 1,\)

which is exactly the Taylor polynomial of \(e^x\). Intuitively, this makes sense and meshes with our earlier observations about Taylor polynomials approximating \(e^x\) at x = 0 as well as possible and orthogonal projections \(P_c(e^x)\) approximating \(e^x\) as well as possible on the interval \([-c,c]\). However, I am not aware of any proof that this happens in general (i.e., no matter what the degree of the polynomial is and no matter what (sufficiently nice) function is used in place of \(e^x\)), and I would love for a kind-hearted commenter to point me to a reference. [Update: user “jam11249” provided a sketch proof of this fact on reddit here.]

Here is an interactive Desmos plot that you can play around with to see the orthogonal projection approach the Taylor polynomial as \(c \rightarrow 0\).